
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


def connect(root):
    # 空树的情况
    if not root:
        return None
    queue = [root]
    while len(queue) > 0:
        queueLen = len(queue)
        pre = queue[0]
        while queueLen > 0:
            node = queue.pop(0)
            if pre == node:
                # 第一个结点
                pass
            else:
                pre.next = node
                pre = pre.next

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            queueLen -= 1
